Le chiffrement asymétrique RSA
⚓︎

Ce système a été inventé en 1977 par trois mathématiciens R.Rivest, A.Shamir et L.Adleman,qui se sont inspirés des idées sur les échanges de clés contenues dans les travaux de Diffie et Hellman.

cal

Regarder la vidéo:

I. Le codage RSA simplifié⚓︎

cal

Le chiffrement RSA est asymétrique :

il utilise une paire de clés (des nombres entiers) composée:

d'une clé publique pour chiffrer.
d'une clé privée pour déchiffrer.

Les deux clés sont créées par une personne, souvent nommée par convention Alice, qui souhaite que lui soient envoyées des données confidentielles:

La clé publique est accessible à tous. Cette clé est utilisée par ses correspondants (Bob, etc.) pour chiffrer les données qui lui sont envoyées.
La clé privée est quant à elle réservée à Alice, et lui permet de déchiffrer ces données.

Une condition indispensable est qu'il soit « calculatoirement impossible » de déchiffrer à l'aide de la seule clé publique, en particulier de reconstituer la clé privée à partir de la clé publique, c'est-à-dire que les moyens de calcul disponibles et les méthodes connues au moment de l'échange (et le temps que le secret doit être conservé) ne le permettent pas.

Le chiffrement RSA est souvent utilisé pour communiquer une clé de chiffrement symétrique, qui permet alors de poursuivre l'échange de façon confidentielle :

Bob envoie à Alice une clé de chiffrement symétrique qui peut ensuite être utilisée par Alice et Bob pour échanger des données.

II. Génerer et utiliser une paire de clés (clé publique, clé privée)⚓︎

Prérequis d'arithmétique modulaire (maths expertes)

a. Les congruences

Exemple

Il est 22h, quelle heure sera-t-il 8h plus tard ?

Si vous avez répondu 6h (et pas 30h à la question précédente), vous venez de faire de l'arithmétique modulaire, en effet vous n'avez conservé que le reste de la division euclidienne par 24:
30 = 1 × 24 + 6 on écrira que 30 ≡ 6[24] et on lira 30 est égal à 6 modulo 24 ou 30 est congru à 6 modulo 24.

Vérifions que 53 ≡ 5[24]. En effet 53 = 2 × 24 +5

Question

a. Compléter : 103 ≡ ...[24]

b. Compléter : 13 ≡ ...[5]

c. Compléter : 42 ≡ ...[7]

Solution

a. 103 ≡ 7[24] car 103 = 4 × 24 + 7

b. 13 ≡ 3[5] car 13 = 2 × 5 + 3

c. 42 ≡ 0[7] car 42 = 6 × 7 + 0

b. Nombres premiers et nombres premiers entre eux

Question

Rappeler la définition d'un nombre premier. Les nombres suivants sont-ils premiers (justifier) : 12, 21, 29, 1 ?

Solution

Un nombre premier est un nombre qui a exactement deux diviseurs : 1 et lui même

12 n'est pas premier car en plus de 1 et 12, il a aussi comme diviseur 2
21 n'est pas premier car en plus de 1 et 21, il a aussi comme diviseur 3
29 est premier, il n'a que 1 et 29 comme diviseurs
1 n'est pas premier : il n'a qu'un seul diviseur : 1

Question

Rappeler la définition de nombres premiers entre eux.
- 12 et 5 sont-ils premiers entre eux?
- 33 et 27 sont-ils premiers entre eux?

Solution

On dit que deux nombres sont premiers entre eux lorsque leur PGCD vaut 1.

12 et 5 sont premiers entre eux
33 et 27 ne sont pas premiers entre eux car 33 = 11 × 3 et 27 = 9 × 3. Leur PGCD est égal à 3.

Voici comment générer et utiliser une paire de clés RSA (c'est à dire une clé publique et sa clé privée correspondante):

Étape 1:

Alice choisit 2 grands nombres premiers p et q. Dans la réalité ces nombres seront vraiment très grands (plus de 100 chiffres).

Dans notre exemple, nous prendrons p = 3 et q = 11.

Étape 2:

Alice multiplie ces deux nombres p et q et obtient ainsi un nombre n appelé module de déchiffrement: n = p×q

😊 Il est très facile pour Alice de calculer n en connaissant p et q.
😢 Il est extrêmement difficile pour Marc de faire le travail inverse : trouver p et q en connaissant n prend un temps exponentiel avec la taille de n.

C'est sur cette difficulté (appelée difficulté de factorisation) que repose la robustesse du système RSA.

Dans notre exemple, nous prendrons n = 3 × 11 = 33.

Étape 3 : Alice crée sa clé publique

On note le nombre f = (p−1)×(q−1). C'est l'indicatrice d'Euler.

Alice choisit un nombre e appelé exposant public(par exemple 3, 17, 257 ou 65537), qui doit être premier avec le nombre 𝑓 = (p−1)×(q−1).

Dans notre exemple, (p−1)×(q−1) = 20, Alice choisit donc e = 3. (mais elle aurait pu aussi choisir 7, 9, 13...).

Le couple (e, n) sera la clé publique d'Alice. Elle la diffuse à qui veut lui écrire.

Dans notre exemple, la clé publique d'Alice est (3, 33).

Étape 4 : Alice calcule sa clé privée

On trouve l'exposant privé d en calculant l'inverse de e modulo f, c'est-à-dire que le reste de la division euclidienne de e × d par 𝑓 soit égal à 1.

Alice calcule maintenant sa clé privée : elle doit trouver un nombre qui vérifie l'égalité e × d ≡ 1[𝑓]

Dans notre exemple, comme 7 × 3 ≡ 1[20], ce nombre d est égal à 7.

Le couple (d, n) sera la clé privée d'Alice. Elle ne la diffuse à personne.

Dans notre exemple, la clé privée d'Alice est (7, 33).

Étape 5 : Bob envoie un message chiffré à Alice avec la clé publique d'Alice

Supposons que Bob veuille écrire à Alice pour lui envoyer le nombre 4. Il possède la clé publique d'Alice, qui est (3, 33).

Il calcule donc 4³ modulo 33, qui vaut 31. C'est cette valeur 31 qu'il transmet à Alice.

4³ ≡ 31[33]

🐍 Script Python

>>> (4**3) % 33
31

Étape 6 : Alice déchiffre le message envoyé par Bob avec sa clé privée

Alice reçoit la valeur 31. Il lui suffit alors d'élever 31 à la puissance 7 (sa clé privée), et de calculer le reste modulo 33

31⁷ = 27512614111
27512614111 ≡ 4[33]

🐍 Script Python

>>> (31**7) % 33
4

Elle récupère la valeur 4, qui est bien le message original de Bob.

cal

clé privée et clé publique

Le couple (e, n) constitue la clé publique.
Le couple (d, n) constitue la clé privée.

Questions:

Alice veut écrire à Bob. Soit le couple de nombre premiers (p, q) avec p = 5 et q = 13.

Calculer n et 𝑓.

Solution:

n = 5 × 13 = 65
𝑓 = 4 × 12 = 48

Justifier que (9, 65) ne peut pas être une clé publique.

Solution:

Pour que (e, n) soit une clé publique, il faut que e et 𝑓 soient premiers entre eux. Or le PGCD de 9 et 48 est 3.
9 et 48 ne sont donc pas premiers entre eux.

Vérifier que (11, 65) est une clé publique. C'est la clé publique de Bob

Solution:

Pour que (e, n) soit une clé publique, il faut que e et 𝑓 soient premiers entre eux. Or le PGCD de 11 et 48 est 1. 11 et 48 sont donc premiers entre eux. On peut donc choisir (11, 65) comme clé publique.

Vérifier que 35 est un inverse de 11 modulo 48.

Solution:

35 × 11 = 385. Or 385 = 8 × 48 + 1 Donc 35 × 11≡ 1[48] On dit que 35 est un inverse de 11 modulo 48.

🐍 Script Python

>>> 385 % 48
1

En déduire la clé privée de Bob.

Solution:

La clé privée de Bob est donc (35, 65).

Chiffrer le nombre secret d'Alice 17 avec la clé publique de Bob. C'est ce nombre qu'Alice envoie à Bob

Solution:

🐍 Script Python

>>> (17**11) % 65
23

17 sera chiffré par 23. Alice envoie donc 23 à Bob.

Déchiffrer le nombre reçu par Bob.

Solution:

Bob doit déchiffrer 23. Pour cela il utilise sa clé privée qui (35, 65) :

🐍 Script Python

>>> (23**35) % 65
17

Bob a bien déchiffré le nombre 17, qui était celui qu'Alice voulait lui envoyer

III. Envoyer un message avec la clé publique⚓︎

Pour coder la phrase "Bienvenue au LDM", on utilise la fonction ord pour connaitre le code Unicode de chaque caractère :

Exécuter le script ci-dessous:

Puis nous coderons chaque lettre l'une après l'autre.
Par exemple pour la deuxième lettre i : 105.

La lettre i sera donc codée par le nombre $105^{e}$ % n

Note: On utilisera la fonction pow. On pourrait aussi écrire $105^{e}$ % n mais plus tard on utilisera des grands nombres et seule la fonction pow sera assez efficace pour cela.

Exécuter le script ci-dessous:

Compléter le script ci-dessous:

La fonction renverra une chaîne de caractères contenant les nombres codés, séparés par un espaces " ".
On prendra garde à enlever le dernier caractère s'il s'agit d'un espace.

Évaluations restantes : 5/5

.128013n=ksAo 5alFi/(1v8hP6,R-g7+qybedrctfw)p:]é[032m4è;S9u050F0E0I0j0m0k0e0h0H0k0j0e0e0c010I0m0M010406050e0!0U0U0j0G0C040Y0g0k0!0^0g0b050n0 1113150}0M04051l1e1o0n1l0}0F0m0q0-0/0;0?0s0m0y0s0k1C0s0I0{050(0D0k0E1x0:0=011B1D1F1D0I1L1N1J0I0G1m0I0s0-180e0M0j0b0?0T011P1z010J0*0E0b0j0U0E1J1,1.1?1R1_1N1|1~0{0a0h0t0G0g0M0g0e0m1b0b0h0$1*0G0G0E0H2j1e210b1m0n1(2w1#1%1$1K0F230?1F0b1{2g1J1u1w0.1Q2G0m2I0b0g2M1J0M2p1m2u2w2!0~1-2k2O1@2T0G120k0{0h0p2t2(0|2%222*1R2,2.2:0T2?1.2^2u2F012}0j2/040h0S312v0}342{0?37390h0V3d332(353j2:0i3n3f3p3h360g2-382:0u3u2_2)1y2|3z2~3a0z3E3g3H3i3J3B3a0r3N3w3P3y3A3k0Z3V2`3X3r040p0R3n1p2Y1e2M2z0F1%2E3x0H2U1 1m3;1n3/2$1f2@053`0$2Z3W2P010d0{0$0J3-3O490K2:4f482+0J0{0w0Y0f4k3%490`040o4s3G490b0{0M0s0G0:0E4y354v0v3n0h3F3q0{4H42324O3x4K4M4U3(0{1d4S2v4Y4u0{0L0N3$4z1@4i3a0h4=4I3x0e0F0{020B0!0g0I0X4|4~50524 0X0l1c2r0m1c0h4}0m0h2X1{2E1{5g131}0W1#0E0,0!2I0-0s0)5t2m0H5m2r0W2p0,5w2h5d0!1O1N0,2T0U0D5D0h1O0%0h2k5S2p0b0q0g0m5J1O1~0;0j0y1O0H140M0I0P4-354_2:4=2b0G0P3`0b1u2j0e0N5g4E4G2l1O0I0C0M1O0e1#0v5Q5Q0I5T650h67695Q0b0^0E0G5;4^4`4;4=0t2g0I5|5~5b0b60624F0e5+1B0J0J5`1O2m6k6a1#6r3X5?6u0h55544}566W0X3u065^4N4g2+0{454R2!6)4l1R0g0{0c4X6*1R0e0p4{030S0Z516 713u6(4(1@4b040J3z6_6;3i6,137d4t1@0g4:2R7i4.2|4C636G4@3X4v4,4$6U6(6%6(5^777q046-7o356?046^7y6:7j7F7H7N7E0?7K0A7I3x0b0D0{6b6q7y7T014v4x7(6`3i7!042f0K7u4)4w7@2+7:3z0F7`1R7+7 7f7G7h7-7e7*4*4L7S7.364Q8288048a6/7)4B044#2$8c4v0L0L7X3X7V8t490e1;046!6V6Y504M7B4?8c792p0I0!0G8n2@7O7p837R8o874v0Q7x8U7P7U0{0x8f0U0m0{2=868!8g0O3E0n6-2w5h2w3~2x3?1e2A8}0j1M0E8_1v2^0n0$0(0*0e04.

Cryptez le mot "Spécialité" avec la clé publique (e, n) = (23, 3128548201)

IV. Déchiffrer un message avec la clé privée⚓︎

On obtient le message décrypté en calculant le reste de la division euclidienne de $c^d$ par $n$: ($c^d$ % n)

Note: On utilisera la fonction pow. On pourrait aussi écrire $c^{d}$ % n mais plus tard on utilisera des grands nombres et seule la fonction pow sera assez efficace pour cela.

Exécuter le script ci-dessous:

On pourra utiliser la méthode split :

Exécuter le script ci-dessous:

Compléter le script ci-dessous:

Évaluations restantes : 5/5

.128013n=kso 5alFi/(1v8hP6,g7+qybedrctfw)p:é032m4.è;S9u050C0B0F0i0l0j0e0g0E0j0i0e0e0c010F0l0J010406050e0W0P0P0i0D0z040U0f0j0W0;0f0b050m0{0}0 110_0J04051h1a1k0m1h0_0C0l0p0)0+0-0/0r0l0v0r0j1y0r0F0@050!0A0j0B1t0,0.011x1z1B1z0F1H1J1F0F0D1i0F0r0)140e0J0i0b0/0O011L1v010G0$0B0b0i0P0B1F1(1*1/1N1=1J1^1`0@0a0g0s0D0f0J0f0e0l170b0g0Y1$0D0D0B0E2f1a1}0b1i0m1!2s1X1Z1Y1G0C1 0/1B0b1@2c1F1q1s0*1M2C0l2E0b0f2I1F0J2l1i2q2s2W0`1)2g2K1:2P0D0~0j0@0g0o2p2!0^2Z1~2$1N2(2*2,0O2/1*2;2q2B012_0i2+040g0N2}2r0_302@0/33350g0Q392 2!313f2,0h3j3b3l3d320f2)342,0t3q2=2#1u2^3v2`360w3A3c3D3e3F3x360q3J3s3L3u3w3g0V3R2?3T3n040o0M3Y3C2L3U3G0o2.1b2:3r3Z3+3#0o2|3:2~1l2U1a2I2v0C1Z2A3t0E2Q1{1i401j3~2Y3{2r05460Y2V3S3+0d0@0Y0G3j3B310H2,4q3K3@0G4n2m1x0G0G2l4v4k1:0?040n4F3?2%0@4h0B4L3*4H0@0u3j0g4r3t0b4n4R314I4V4e364Y3!0@194*4,3+4I0I0K3)4s2,0g4|4$3t0e0C0@020y0W0f0F0T53555759560T0k182n0l184|540l0g2T1@2A1@5n0 1_0S1X0B0(0W2g1`0-0i0v1K0E4B4D0L0u0g1J0(2P0P0A2l0(5q0F0g2g0Z0g2l0b0p0f0l1K1J0g5B0e5D1K0C0L0E100J0F0L0R4_4 51364|270D5:181q2f0e0K1$2i2i0F0z0J1K0e1X5K5T5V2h1K6a6c0g1@0;0B0D5`3T504{4|0s2c0F460b635i0b656j5;6b5U696b6d1X6s3+6u5}4|5c5b545d6T0T3q065~4X4w4N041B6e4Q4*6$4G1N0f0@0c4W4;6(4P4~3T6;045_4:6%2^0@1(1B0F6{4=0@4K706/0/0e1-046X0g6X774T040I3q6#6^72040Y6H5?6@710/6}6?6-7q7d0o52030N0V587G7I7o5~7C014m040G3v7w7c324.0A0E0 7U4M6:4t042N7#4S7r6*0F6,2W6.7$0/4I4^4*6!6#7N7x7W7s2m5=767B7~7z7+3m4z7u837;7O6}0x874Z0A4O0r6r7b7?014I7a2Y7~0b8i042b0H7k1N8p8y3e8u2N8b2:7O8A8m7,3e7X7Z8l8r7V4?4)8c8s4#8J4%4U8g4-044/8P8n4?7n7`7{4}7~7Q2l0F0W0D8$2:7=8K7 7t823A0m4P2s5o2s4a2t421a2w970i1I0B931r2;0m0Y0!0$0e04.

Decryptez le mot "Spécialité" que vous avez crypté précedemment, avec la clé privée (d, n) = (544075879, 3128548201)

V. Casser des clés RSA⚓︎

Voici un code qui permet de décomposer un nombre entier $n$ en deux facteurs :

si n est premier alors la fonction renvoie le couple (1, n)
sinon la fonction renvoie un couple (p, q) tel que $1<p<=q$ et ${p}\times{q}=n$

Exécuter le script ci-dessous:

Quelques commentaires sur cet algorithme:

Dans un premier temps, on a traité les cas particuliers n=2 et n=3.
Ensuite on remarque qui si $n$ est pair, la fonction peut renvoyer le couple (2, n//2).
Pour les nombres impairs, il suffit donc de tester la division de $n$ par les nombres impairs : 3, 5 , 7 ...

Une fois qu'on a trouvé p et q, on peut trouver f et donc d.

Voici un code qui permet de calculer l'inverse de e modulo f:

Exécuter le script ci-dessous:

Compléter le script ci-dessous:

Vous utiliserez les fonctions produit et inverse_modulaire.

Évaluations restantes : 5/5

.128013n=kso 5ali/(1v8_hP6,-g7qybedrctfw)p:é032m4*;S9u050C0B0F0i0k0j0e0g0E0j0i0e0e0c010F0k0J010406050e0V0P0P0i0D0z040T0f0j0V0:0f0b050l0`0|0~100^0J04051g191j0l1g0^0C0k0o0(0*0,0.0r0k0w0r0j1x0r0F0?050Z0A0j0B1s0+0-011w1y1A1y0F1G1I1E0F0D1h0F0r0(130e0J0i0b0.0O011K1u010G0#0B0b0i0P0B1E1%1)1.1M1;1I1@1_0?0a0g0s0D0f0J0f0e0k160b0g0X1#0D0D0B0E2e191|0b1h0l1Z2r1W1Y1X1F0C1~0.1A0b1?2b1E1p1r0)1L2B0k2D0b0f2H1E0J2k1h2p2r2V0_1(2f2J1/2O0D0}0j0?0g0n2o2Z0@2Y1}2#1M2%2)2+0O2.1)2:2p2A012^0i2*040g0N2|2q0^2 2?0.32340g0Q382~2Z303e2+0h3i3a3k3c310f2(332+0t3p2;2!1t2@3u2_350x3z3b3C3d3E3w350p3I3r3K3t3v3f0U3Q2=3S3m040n0M3i1k2T192H2u0C1Y2z3s0E2P1`1h3,1i3*2X1a2/053=0X2U3R2K010d0?0X0G3(3J440H2+4a432$0G0?0E1L0B0D0q0D0e0i4f3Y440=040m4s3B440b0?0B4y304v0u3i0g3A3l0?183}2}4K3s4v0I0K3X4z1/4d350g4!4E3s0e0C0?020y0V0f0F0S4+4-4/4;4.0S270L3=0b1p2e0e0K1s0L0g0J0V1H0k4,1J0i0o2l0g1J0Y0g2f2h0F0z0J5f0b0:4m4V304(2+4!262b0F4|4~0k175052540D1q0L5a5c0E2g5e0F5h2g1J5k5m5e5o0k5q4O394Q3S5t4Z4!4@4?4,4^5)0S3p065v4J4b2$0?0J4$3S4G4I5!4A0?0y5}5?1M0f0?0c624g2@5^280C0V2d5`4u0?4x5Y424t5@044N2X630.4S3p5;5~6n496k5=690.6504676z6w1M4v6j6q6B315^6g1/6D0v6P1M0P0k0?2-6k6H6s0?0I6T6C0?0R6(016J6,4B04616Z6r016R6,6V6X6,6t6k5:5v6!6N040C686m6466764W6a042M5c4p0B0q0P2P0V0*0k2k6}6i6/4C7p044H6G6@6:6y6L776#046%6z06704#6@46042k0F0V0D6p3~6@6.6?6M6:757U7B6-0?7v2V6A7Z6:7Q4P7S6$3z0l400B2r2S7=3+1q3-2u2x2s0i1H7^0l3,0^820Y0!0$04.

Sécurité du codage RSA

Mais alors ... est-ce que la signature RSA est sécurisée ou pas ? On vient de casser une clé RSA, après tout ! La réponse est : RSA est sécurisé quand on utilise des clés assez grandes. Quand on génère des clés RSA avec des nombres p et q suffisamment grand (donc n est grand aussi), les opérations que doivent effectuer les « gentils » (signature et vérification) sont un peu plus longues à effectuer.

Mais les opérations nécessaires pour casser une clé RSA (en gros, la factorisation de n) demandent, elles, beaucoup plus de temps.

cal

On remarque que, si ce temps est très court pour de petits nombres (à 3 chiffres), il devient vite important pour des grands nombres. En fait ces nombres n'ont pas été choisis au hasard : ils sont formés du produit de deux nombres premiers.

Voilà donc pourquoi casser de véritables clés RSA n'est pas aussi simple que ce que l'on vient de voir, et pourquoi RSA est en fait sécurisé: quand la puissance de calcul des ordinateurs augmente tellement que casser les clés actuelles risque de devenir faisable, on augmente très légèrement la taille des clés: RSA devient légèrement plus long à utiliser mais beaucoup plus difficile à casser.

Pour information, la taille de clé recommandée aujourd'hui pour RSA est d'avoir un n de ... 2048 bits minimum.

Nous avons donc la une fonction à sens unique :
- il est très facile de calculer le produit de deux nombres premiers.
- il est difficile (voir impossible en un temps raisonnable), dès que ces nombres sont grands, de décomposer ce produit en deux facteurs de nombres premiers. Le temps que prend cette factorisation croît exponentiellement avec la longueur de la clé.

BILAN

Il faut enfin réaliser une fiche de cours (sur une feuille simple) en faisant apparaitre les notions importantes de ce cours :

Connaitre le principe des chiffrements asymétriques.
Connaitre le principe du codage RSA.

Le chiffrement asymétrique RSA⚓︎

I. Le codage RSA simplifié⚓︎

II. Génerer et utiliser une paire de clés (clé publique, clé privée)⚓︎

III. Envoyer un message avec la clé publique⚓︎

IV. Déchiffrer un message avec la clé privée⚓︎

V. Casser des clés RSA⚓︎

Le chiffrement asymétrique RSA
⚓︎